The present invention relates to telecommunications networks, and more particularly to multicast transmissions.
FIG. 1 illustrates a telecommunications network having network nodes 110 interconnected by links 130. Nodes 110 include switches or routers 110R.1, 110R.2, . . . and end stations 110E.1, 110E.2, . . . . Each link 130 may be a wired or wireless link or may be a network (e.g. LAN, i.e. Local Area Network). A switch may forward packets 210 (FIG. 2) based on the packets' L2 (layer 2) destination address DA2 and/or L3 (layer 3) destination address DA3. As shown, the packet also has a layer-2 source address SA2 and may have a layer-3 source address SA3. As used herein, the terms “switch” and “router” are synonymous and refer to any computer that forwards packets transmitted over a network, but the term “router” is preferred for layer 3 forwarding.
A multicast protocol may allow a packet's destination address (DA2 and/or DA3) to specify a group of nodes 110. (Actually, an address usually identifies a node's network interface; when we say that an address identifies a node, we mean that the address identifies one or more of the node's interfaces.) A multicast transmission to a group of nodes conserves network resources compared to separate, unicast transmissions to each node. For example, if nodes 110E.1, 110E.2, 110E.11 form a group, and node 110E.10 sends a packet to the group, then only one copy of the packet is delivered to router 110R.1 and then to router 110R.2. Router 110R.2 sends one copy of the packet to router 110R.5 for delivery to node 110E.11, and sends another copy to router 110R.4 for delivery to the remaining group members. Network resources are conserved compared to sending a separate copy of the packet from source node 110E.10 to each of the three group members.
Well-known multicast protocols for IP (Internet Protocol) networks include PIM (Protocol Independent Multicast) and IGMP (Internet Group Management Protocol). IGMP version 3 is described for example in RFC 4604 (Internet Engineering Task Force (IETF), August 2006). IGMP version 2 is described in RFC 2236 (IETF, November 1997). Sparse-Mode PIM is defined by RFC 4601 (IETF August 2006). RFCs 4604, 2236, and 4601 are incorporated herein by reference. IGMP defines how a node 110 can join or leave a multicast group. PIM defines how IP routers 110R set up multicast paths for distribution of multicast packets.
IP addresses are layer-3 addresses, and a multicast group in PIM and IGMP is defined by an IP address; in IPv4 (version 4), the multicast address is any IP address in the range of 224.0.0.0 to 239.255.255.255 inclusive. For example, suppose that node 110E.1 wishes to join a group with address 225.1.1.1. Then node 110E.1 sends an IGMP packet of type Report (report group membership) to the node's local multicast router, e.g. 110R.3. Router 110R.3 uses its database (DB) 140 to make packet-forwarding decisions, and router 110R.3 updates this database in response to the IGMP packet. More particularly, DB 140 (FIG. 3) includes a membership list 140L of all group members for which the router serves as a local multicast router (such a router is called “Designated Router” in PIM). The membership list 140L is updated when the router receives an IGMP message of type Report or Leave (leave the group), or when the router does not receive a repeated Report message from a group member within predefined time (the group members periodically re-send Reports in order to retain the group membership). In the example of FIG. 3, the list 140L includes group members 110E.1, 110E.2 for group 225.1.1.1.
DB 140 also includes a Multicast Routing Information Base (MRIB) 140P constructed based on the PIM protocol and used by the router to determine the outgoing interfaces for multicast packets. An exemplary MRIB entry 144 (such as 144.1, 144L.2, or 144L.3) includes:                Source address “SA” (layer 3 address, matched against the packet's source address SA3). The asterisk (*) is a wild card meaning that the entry 144 applies to any source.        Group Address “GA” (225.1.1.1 for example).        Incoming interface “iif”. An interface can be a physical interface (e.g. a port number of a physical port), but an interface may also include virtual information, e.g. the virtual LAN (VLAN). In entry 144.1, the incoming interface is a VLAN with VLAN ID of 200. This corresponds to VLAN 150.1 in FIG. 1. This VLAN is defined for link 130 connecting the router's port P5 to port P1 of router 110R.4. Link 130 may be connected to additional nodes (not shown), and VLAN 150.1 is defined for the traffic between the two routers so that the routers can distinguish this traffic from the traffic to and from other nodes connected to the link. (We will sometimes refer to VLAN 150.1 as VLAN 200; in this document, a VLAN can be referred to by its reference numeral (such as 150.1) or its ID (such as 200).)        Outgoing interface “oif” for the packet, and actions to be performed in packet forwarding. (For example, the actions may specify the layer-2 addresses for packet forwarding.)        
According to entry 144.1, if a multicast data packet (as opposed to control packets) is received on VLAN 200, and has the DA3 destination address of 255.1.1.1, then the packet is forwarded on VLAN 150.2 (having VLAN ID of 10) on ports P1, P2 (for delivery to group members 110E.1, 110E.2).
According to PIM, multicast packets are distributed to the group members via one or more distribution trees rooted at pre-determined routers 110. For example, a distribution tree can be rooted at a router called the Rendezvous Point (RP). Assuming for example that the router 110R.2 is the RP, a multicast data packet received by router 110R.3 on VLAN 150.2 (VLAN 10) should be forwarded to router 110R.4 for delivery to the RP. This is accomplished via entry 144L.2: if a packet is received on VLAN 10, and has the DA3 destination address of 255.1.1.1, then the packet is forwarded on VLAN 200. (We use the letter L in 144L.2 to mark entries for locally sourced multicast packets, i.e. packets sourced by nodes for which the router is a local multicast router; such nodes are called “local nodes” below; local nodes may or may not be directly attached to the router.)
Similarly, per entry 144L.3, if a multicast data packet is received on VLAN 20 (VLAN 150.3) and has the DA3 address of 255.1.1.1, then the packet is forwarded to the RP on VLAN 200. An entry of type 144L is created for each incoming interface that can receive locally sourced multicast data packets.
Also, multicast data packets received on VLANs 10 and 20 should be forwarded to the local group members 110E.1, 110E.2 directly rather than through the RP. This is because the RP does not transmit the packets on the interfaces on which the packets are received, and therefore will not return the packets to the routers from which the packets are received. Therefore, router 110R.3 uses a non-PIM mechanism to forward the locally-sourced packets to local group members. One possible mechanism is simply to flood such packets on local VLANs (such as VLANs 10 and 20). This however undesirably increases network traffic. To avoid flooding, the locally sourced multicast data packets are sometimes forwarded only to the group members, i.e. only to nodes in the list 140L for the group.
To speed up and simplify the forwarding process, the router builds a forwarding database 140F (shown in FIG. 3 as MFIB, which stands for Multicast Forwarding Information Base). This database combines all the information needed for fast forwarding decisions. For the packets arriving on VLAN 200, the database entry 148.1 provides the same information as entry 144.1. For the packets arriving on VLAN 10, the entry 148L.2 shows that the packets must be forwarded on VLAN 200 (to the RP, per entry 144L.2) and must also be forwarded on VLAN 10 (ports P1, P2) to the local group members in list 140L. In this way, the forwarding can be performed using the MFIB 140F without consulting the list 140L.
Similarly, per entry 148L.3, the packets arriving on VLAN 20 are to be forwarded on VLAN 200 to the RP and on VLAN 10 (ports P1, P2) to the local group members.
As noted above, forwarding of locally sourced packets to the local group members is based on the IGMP messages. More particularly, DB 140 includes “IGMP snooping” database 140G. Each entry 160 of IGMP snooping database 140G has the same types of fields as entries 144 and 148. Exemplary entry 160.1 shown in FIG. 3 specifies that if a packet has any source address SA3 (as indicated by wild card *), and has IP destination address 255.1.1.1, and the packet arrived on VLAN 10, then the packet should be forwarded on VLAN 10 (ports P1 and P2). Entry 160.2 specifies the same forwarding for the packets arriving on VLAN 20. The router builds IGMP snooping database 140G based on the IGMP messages. The router combines MRIB 140P and IGMP snooping database 140G to construct MFIB 140F. When a multicast data packet arrives, the router searches MFIB 140F for a matching entry (i.e. an entry having the same source address (or the wildcard) as the packet's SA3, the same incoming interface as the interface on which the packet arrived, and the same group address as the packet's DA3). If a matching entry is found, the router forwards the packet based on the entry's outgoing interface, and the router does not need to consult the list 140L. If no matching entry is found, then the router floods the packet on the same VLAN on which the packet arrived, and/or floods the packet on other VLANs, and/or consults other information (e.g. list 140L), depending on the router and the router's configuration.
A router is sometimes conceptualized as having a “forwarding plane” and a “control plane”. The forwarding plane is the router portion that receives and transmits packets. The control plane is the router portion that builds and maintains various databases (such as 140) and performs other control functions (that differ from switch to switch). In particular, the control plane processes control messages such as IGMP messages: such messages are sent to the control plane by the forwarding plane. The forwarding plane forwards data packets based on databases such as MFIB 140F that are optimized for forwarding (a similar database can be provided for unicast forwarding). If additional action may be needed to process a packet, the packet is sent to the control plane.
FIG. 4 illustrates an exemplary sequence of events. At step 310, group members 110 (e.g. nodes 110E.1, 110E.2, 110E.11) inform their respective local multicast routers (such as 110R.3 and 110R.5), via IGMP, that these nodes are members of a group (e.g. group 225.1.1.1). This is accomplished by each group member sending an IGMP Report packet 314 to the node's local multicast router. IGMP Report packet 314 is an IP packet having the same general format as in FIG. 2, and in particular the packet 314 includes the destination addresses DA3, DA2 of the local multicast router's interface(s), and the packet includes the source addresses SA2, SA3 of the sending node (“the sender”, i.e. the group member). These addresses are not shown in FIG. 4. The Internet Protocol requires a packet to have the Protocol Number field 210P, which must be 2 for IGMP; and Type field 210T, which indicates whether the sender 110 is reporting its membership in the group or is leaving the group. The Type 210T is “Report” in the example shown. The packet's Group Address field 210G is the group address (225.1.1.1). In IGMP version 3, the packet may also include the L3 source addresses from which the sender desires to receive multicast transmissions (these addresses would be inserted instead of the wildcard “*” in MRIB 140P, MFIB 140F, and IGMP snooping database 140G).
At step 320, the local multicast routers updates their DB 140 (databases 140L, 140P, 140G, 140F) as needed. If the IGMP Report sender 110 is the only member of the group in list 140L, then the router notifies all other multicast routers via PIM (PIM's Join message) that the router wishes to receive packets addressed to the group.
FIG. 5 illustrates a possible state of DB 140 of router 110R.3 after execution of step 320 for group members 110E.1, 110E.2. List 140L and IGMP snooping database 140G are as in FIG. 3. MRIB entry 144.1 is the same as in FIG. 3; this entry is used to forward non-locally-sourced traffic. However, it is assumed that the router has not received a locally sourced data packet addressed to the group. Therefore, entries 144L are absent for the group.
According to PIM, if router 110R.3 starts receiving locally sourced data packets addressed to a group before the router's forwarding database is provisioned to forward such packets to non-local group members, the router must encapsulate the packets into unicast packets and forward the encapsulated packets to the RP via unicast transmission. (This is called Register operation.) When the RP receives an encapsulated packet, the RP will send a PIM Join message towards router 110R.3. (This is called “Register Stop”.) The Join message will travel to router 110R.4 and then 110R.3, and in response to the Join message the routers will provision their MRIBs and MFIBs to forward the group's data packets to the RP. In particular, router 110R.3 will create entries 144L.2, 144L.3 as in FIG. 3.
MFIB 140F of FIG. 5 is formed from MRIB 140P and IGMP snooping database 140G. MFIB 140F is the same as in FIG. 3 except that it is not provisioned to forward locally sourced data packets to the RP. In particular, in entries 148L.2 and 148L.3, the outgoing interface includes only local VLANs. However, in addition to forwarding the locally sourced packets on the local VLANs, the forwarding plane should be configured to send such packets to the control plane for the Register operation. In some routers, this is accomplished as follows.
First, note on terminology: If an entry such as 144, 148, or 160, has a wildcard for the source address, the entry is sometimes referred to as (*,G). If the source address is specified, the entry is called (S,G). In FIGS. 3 and 5, all the entries are (*,G). There can be multiple entries for the same group and incoming interface, with different source addresses. Routers prefer to forward packets based on (S,G) entries, i.e. the entries having the same source addresses as the packets' SA3 addresses. If there is no matching (S,G) entry for a packet but there is a matching (*,G) entry, then the packet is forwarded based on the (*,G) entry.
In some routers, the Register operation is initiated as follows. Whenever the forwarding plane forwards a packet based on an (*,G) entry, the packet is also sent to the control plane. In the example of FIG. 5, all the IGMP snooping entries 160 are (*,G), and so are the MFIB entries; there are no (S,G) entries. Therefore, when a locally sourced packet arrives, it is forwarded to local group members per an MFIB entry 148L, and in addition the packet is sent to the control plane. The control plane searches MRIB 140P, finds a matching MRIB entry for the packet, and initiates the Register operation.
However, if the IGMP snooping plane includes an (S,G) entry, then the MFIB 140F may include an (S,G) entry 148L for locally sourced traffic. In this case, the Register operation is initiated as follows. Each entry 148 includes an indicator (called a “HIT bit”, not shown) indicating whether or not the entry is being used for forwarding a packet. The control plane polls (periodically checks) the HIT bits for all the entries 148L. If for any entry 148L the HIT bit indicates that the entry is used for forwarding, then the control plane checks the MRIB, and if the MRIB is not provisioned for the locally sourced traffic addressed to the group, the control plane instructs the forwarding plane to send the packet to the control plane. The control plane then initiates the Register operation on the packet.
At step 330, a network node 110 (e.g. 110E.10 or 110E.5) sends a multicast packet to the group (i.e. with DA3 address of 225.1.1.1). At step 340, the packet reaches the local multicast router, e.g. 110R.3 or 110R.5. At step 350, the local multicast router forwards the packet to the respective group members per MFIB 140F.
Improved multicast schemes are desirable.